package sorter;

/**
 * 计数排序：适用于固定范围的整数排序。假设数组最大值为 max，最小值为 min，则创建大小为 max-min+1 的数组 countArr 进行收集操作。
 * 遍历原数组，对一个数 num，countArr[num-min]++。
 * 遍历 countArr，将收集到的数按顺序添加到 arr。
 * 时间复杂度：找到最大最小值O(n)，收集O(n)，释放O(n)，因此时间复杂度O(n)。
 * 稳定性：可以稳定。
 * @author Zhang Ziyi
 */
public class CountSorter implements Sorter{
    @Override
    public void sort(int[] arr) {
        int[] minAndMax = findM(arr);
        int min = minAndMax[0], max = minAndMax[1];
        // 创建收集数组
        int[] countArr = new int[max - min + 1];
        for (int num : arr) {
            countArr[num - min]++;
        }
        // 添加到 arr
        int p = 0;
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                arr[p++] = i + min;
                countArr[i]--;
            }
        }
    }

    /**
     * 查找最值
     */
    private int[] findM(int[] arr) {
        int[] minAndMax = new int[2];
        int minIndex = 0, maxIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
                continue;
            }
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        minAndMax[0] = arr[minIndex];
        minAndMax[1] = arr[maxIndex];
        return minAndMax;
    }
}
